public class No054 {
    /**
     * 给定一棵二叉搜索树，请找出其中的第k小的结点。
     * 例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    int count = 0;

    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null) return null;
        TreeNode treeNode;
        // 中序遍历
        treeNode = KthNode(pRoot.left, k);
        if (treeNode != null) {
            return treeNode;
        }
        if (++count == k) {
            return pRoot;
        }
        treeNode = KthNode(pRoot.right, k);
        return treeNode;
    }
}
